package com.lizk.graph.noweight;

import java.util.ArrayList;
import java.util.List;

/**
 * 邻接矩阵(AdjacencyMatrix)
 * 适合表示稠密的图,边较多
 *   | 0 1 2 3
 * -----------
 * 0 | 0 1 0 0
 * 1 | 0 0 1 0
 * 2 | 0 0 0 1
 * 3 | 0 1 0 0
 * 以上矩阵1的位置表示对应的两个节点相连
 * 0的位置表示对应的两个节点不相连
 *
 * 邻接表(AdjacencyTable)
 * 适合表示稀疏的图,边较少
 * 0 | 1
 * 1 | 0 2 3
 * 2 | 1 3
 * 3 | 1 2
 * 第一行表示0节点跟1节点相连
 * 第二行表示1节点跟0,2,3三个节点相连
 *
 * @author lizhikui
 * @date 2020/2/15 14:25
 */
public class AdjacencyList implements NoWeightGraph<Integer> {
    int column4Iterator;
    int row4Iterator;
    boolean directed;
    List<Integer>[] g ;

    public AdjacencyList(int n, boolean directed){
        g = new List[n];
        this.directed = directed;
        for (int i = 0; i < g.length; i++) {
            g[i] = new ArrayList<>();
        }
    }

    @Override
    public void iterator(int row){
        this.row4Iterator = row;
        this.column4Iterator = 0;
    }

    @Override
    public boolean hasNext() {
        return column4Iterator < g[row4Iterator].size();
    }

    @Override
    public Integer next() {
        return g[row4Iterator].get(column4Iterator++);
    }

    @Override
    public void addEdge(int row, int col) {
        check(row,col);
        if (!hasEdge(row,col)){
            g[row].add(col);
            if (row != col && !directed){
                g[col].add(row);
            }
        }
    }

    @Override
    public boolean hasEdge(int row, int col) {
        check(row,col);
        return g[row].contains(col);
    }
    private void check(int row, int col){
        assert row >= 0 && row < g.length ;
        assert col >= 0 && col < g.length;
    }
}





